#include <iostream>
#include <thread>
#include <vector>
#include <string>

typedef __int128 int128_t;

// 打印int128的辅助函数
void print_int128(int128_t value) {
    if (value == 0) {
        std::cout << "0";
        return;
    }
    std::string str;
    bool negative = value < 0;
    if (negative) value = -value;
    while (value > 0) {
        str.push_back('0' + static_cast<char>(value % 10));
        value /= 10;
    }
    if (negative) str.push_back('-');
    
    std::cout << str;
}

// 计算数字各位乘积
int128_t digit_product(int128_t number) {
    int128_t product = 1;
    while (number > 0) {
        int128_t digit = number % 10;
        product *= digit;
        number /= 10;
    }
    return product;
}

// 验证条件是否满足
void check_condition(int128_t n) {
    int128_t n_squared = n * n;
    int128_t n_plus_1_squared = (n + 1) * (n + 1);
    if (digit_product(n_plus_1_squared) == n_squared) {
        std::cout << "Found: n = ";
        print_int128(n);
        std::cout << std::endl;
    }
}

// 线程工作函数
void thread_worker(int128_t start, int128_t end) {
    const int128_t report_interval = 10000000000; // 10^10
    int128_t count = 0;
    
    // 确保从奇数开始
    if (start % 2 == 0) start += 1;
    
    for (int128_t n = start; n <= end; n += 2) {
        check_condition(n);
        
        if (++count >= report_interval) {
            std::cout << "Progress: ";
            print_int128(n);
            std::cout << std::endl;
            count = 0;
        }
    }
}

int main() {
    const int THREADS = std::thread::hardware_concurrency();
    int128_t MAX_N = 10000000000000000000000; // 10^22
    
    std::vector<std::thread> threads;
    int128_t chunk_size = (MAX_N - 1) / THREADS;
    
    // 确保分块后的起始值为奇数
    int128_t current_start = 1;
    for (int i = 0; i < THREADS; ++i) {
        int128_t end = current_start + chunk_size;
        if (end % 2 == 0) end -= 1;
        
        threads.emplace_back(thread_worker, current_start, end);
        
        current_start = end + 2;
        if (current_start > MAX_N) break;
    }

    for (auto& t : threads) {
        t.join();
    }

    return 0;
}